package lib

import "algorithms/ds"

func init() {
	Probs = append(Probs, Problem{
		Num:         82,
		Discription: "去除链表中存在重复元素的所有元素",
		Level:       2,
		Labels: map[string]int{
			"链表":    1,
			"快慢指针":  1,
			"虚拟头指针": 1,
		},
	})
}

func DeleteDuplicates(head *ds.ListNode) *ds.ListNode {
	if head == nil {
		return nil
	}

	preHead := &ds.ListNode{
		Next: head,
		Val:  -101,
	}
	fast := head.Next
	//slow为当前比较节点的前一个节点，因为被比较的节点可能被删除，所以还需要用虚拟头指针
	slow := preHead
	dupCount := 0
	for fast != nil {
		if fast.Val != slow.Next.Val {
			if dupCount == 0 {
				slow.Next.Next = fast
				slow = slow.Next
			} else {
				slow.Next = fast
				dupCount = 0
			}
		} else {
			dupCount++
		}

		fast = fast.Next
	}

	if dupCount != 0 {
		slow.Next = nil
	} else {
		slow.Next.Next = nil
	}

	return preHead.Next
}
